import sys
import string
import re

def getStatePattern():
    return "(^s[0-9]+) \[label=\"\(?(.*)\"(.*)\"\)?\"\]"
    
def getArcPattern():
    return "(^s[0-9]+) -> (s[0-9]+) \[label=\".*\"\]"

def getStates(line):
    global rules, states, allStates
    result = re.match(getStatePattern(), line)
    if result:
        allStates[result.group(1)] = result.group(2).strip()
        if result.group(2).strip() not in states.values():
            states[result.group(1)] = result.group(2).strip()
        rules[result.group(1)] = result.group(3).strip()
    return ""

def getArc(line):
    global rules
    result = re.match(getArcPattern(), line)
    if result:
        return "  " + result.group(1) + " -> " + result.group(2) + " [label=\"" + rules[result.group(2)] + "\"]\n"
    return line

def removeDuplicateStates(line):
    global states, rules
    result = re.match(getArcPattern(), line)
    if result:
        if result.group(1) in states.keys():
            if result.group(1) == result.group(2):
                rule = "self"
            else:
                rule = rules[result.group(2)]
            return "  " + result.group(1) + " -> " + getEquivalentState(result.group(2)) + " [label=\"" + rule + "\"]\n"
        return ""
    return line

def getState(line):
    global rules, states, allStates
    result = re.match(getStatePattern(), line.strip())
    if result:
        if result.group(1) in states.keys():
            return "  " + result.group(1) + "[label=\"" + states[result.group(1)] + "\"]\n"
        return ""
    return line

def getEquivalentState(state):
    global states, allStates
    if state in states.keys():
        return state
    lookingFor = allStates[state]
    for k, v in states.items():
        if v == lookingFor:
            return k

rules = {}
states = {}
allStates = {}

lines = sys.stdin.readlines()
exit = []
exit2 = []
exit3 = ""

for i in lines:
    getStates(i.strip())

#print rules
#print states
#print allStates

for i in lines:
    exit.append(getArc(i.lstrip()))

for i in exit:
    exit2.append(removeDuplicateStates(i.lstrip()))

for i in exit2:
    exit3 += getState(i)

print exit3
